package com.yangzhe.algorithm.c021;

// 归并排序，填函数练习风格
// 测试链接 : https://leetcode.cn/problems/sort-an-array/

public class Code01_MergeSort_LeetCode {
    /**
     * 1 <= nums.length <= 5 * 104
     * -5 * 104 <= nums[i] <= 5 * 104
     */
    public static int MAXN = 50001;

    public static int[] help = new int[MAXN];

    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 3, 1};
        int[] ints = sortArray(nums);
        for (int anInt : ints) {
            System.out.print(anInt + ",");
        }
    }

    public static int[] sortArray(int[] nums) {
        if (nums.length > 1) {
            mergeSort2(nums);
        }
        return nums;
    }

    // 归并排序递归版
    public static void mergeSort1(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }

        int m = (l + r) / 2;
        sort(arr, l, m);
        sort(arr, m + 1, r);

        merge(arr, l, m, r);
    }

    // 归并排序非递归版
    public static void mergeSort2(int[] arr) {
        // 步长，每次翻倍
        int step = 1;
        int l = 0;
        int m = 0;
        int r = -1;
        // 循环增加步长，知道超出数组边界
        while (step < arr.length) {
            l = 0;
            while (l < arr.length) {
                r = l + 2 * step - 1;
                m = (l + r) / 2;
                // 如果左侧已经超出，则不用merge，因为已经有序
                if (m >= arr.length - 1) {
                    break;
                }
                r = Math.min(r, arr.length -1);
                merge(arr, l, m, r);

                l = r + 1;
            }
            step = step * 2;
        }
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int lIndex = l;
        int rIndex = m + 1;
        int helpIndex = 0;
        // 将左右两边合并到help数组中
        while (lIndex <= m && rIndex <= r) {
            // 哪边小copy哪边到help数组中
            if (arr[lIndex] < arr[rIndex]) {
                help[helpIndex] = arr[lIndex++];
            } else {
                help[helpIndex] = arr[rIndex++];
            }
            helpIndex++;
        }

        // 左右两边总会有一边会剩余
        // 如果左边剩余，把左边剩余的全部copy到help数组中
        while (lIndex <= m) {
            help[helpIndex++] = arr[lIndex++];
        }

        // 如果右边剩余，把右边剩余的全部copy到help数组中
        while (rIndex <= r) {
            help[helpIndex++] = arr[rIndex++];
        }

        // 将help数组覆盖到原数组原来的位置中
        for (int i = 0; i < helpIndex; i++) {
            arr[l + i] = help[i];
        }
    }

}